/*
 * @lc app=leetcode id=31 lang=cpp
 *
 * [31] Next Permutation
 */
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        
        for (int i = len-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                int k = len-1;
                while (k > i) {
                    if (nums[i] < nums[k]) {
                        break;
                    } else {
                        k--;
                    }
                }
                swap(nums[i], nums[k]);
                reverse(nums.begin()+i+1, nums.end());
                return ;
            }
        }

        reverse(nums.begin(), nums.end());
    }

    void prevPermutation(vector<int>& nums) {
        int len = nums.size();
        
        for (int i = len-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                int k = len-1;
                while (k > i) {
                    if (nums[i] < nums[k]) {
                        break;
                    } else {
                        k--;
                    }
                }
                swap(nums[i], nums[k]);
                reverse(nums.begin()+i+1, nums.end());
                return ;
            }
        }

        reverse(nums.begin(), nums.end());
    }
};

